index.md (3495B)
1 +++ 2 title = "Data Link: Error detection/correction" 3 +++ 4 5 # Data Link: Error detection/correction 6 **Errors** 7 8 - errors can be caused by hardware or software 9 - timer that expires if frame not acknowledged, then frame is resent 10 - flow control is feedback-based (receiver sends permission to sender for more data), or rate-based (built-in data send rate limiter) 11 12 Error detection 13 14 - adds enough redundancy so that receiver can detect error and request retransmission, used on highly reliable networks like fiber 15 - a codeword is n-bit unit with m data bits and r check bits 16 - parity bit 17 - add a single bit to the end to make the number of 1s even 18 - a code with a single parity bit can detect single-bit errors 19 - however, not good with burst errors 20 - to improve, interleave — compute parity in order different from transmission order: 21 22  23 24 - checksums 25 - 16-bit Internet checksum — sum of message bits divided into 16-bit words 26 - Fletcher’s checksum — adds product of data and its position to running sum 27 - improved error detection over parity 28 - detects bursts up to N errors 29 - does not detect systematic fuckups 30 - Cyclic redundancy check 31 - based on treating bit strings as polynomials with coefficients of only 0 and 1 32 - polynomial eg. ×32 + x16 + x8+×1 + 1 33 - sender and receiver agree on generator polynomial G(x) in advance, with both high- and low-order bits at 1 34 - append a CRC to end of frame so that polynomial represented is divisible by G(x) 35 - algorithm to send, with generator G(x): 36 37 1. r is degree of G(x) — append r zero bits to end of frame so it now has m+r bits 38 39 2. divide bit string G(x) into bit string from step 1 with long division (subtracting is mod 2, simply XOR) 40 41 3. subtract remainder from bit string in step 1 using mod 2 subtraction, result is checksummed frame to transmit 42 43 - when received, checks if frame is divisible by G(x). if not, the remainder is the error (E(x)/G(x)) 44 45 Error correction 46 47 - adds enough redundancy to be able to correct errors, used on unreliable networks like 802.11 48 - Hamming distance 49 - shortest distance to change one string into another 50 - compute: XOR two bit strings and count number of ones in result 51 - with Hamming distance d, you can detect d-1 errors 52 - Hamming codes ([video](https://youtu.be/373FUw-2U2k)) 53 - if Hamming distance n, we can correct (h-1)/2 errors 54 - bits of codeword are numbered, with 1 at very left 55 - at powers of 2 are check bits, others are data 56 - sender: 57 58 1. expand locations into powers of 2 59 60 2. decide Value of check bit in location 2i by mod 2 adding all bits with 2i in expansion 61 62 - receiver: 63 64 1. Redo all bit computations 65 66 2. For even parity, each check result should be zero. If not, an error has been detected. 67 68 - check bits for whole message are error syndrome 69 - convert to decimal n, then nth bit is error 70 71  72 73 - Convolutional code 74 - encoder processes input bits & generates output bits 75 - output depend's on current and previous input bits (constraint length) 76 - encoder has memory, e.g. in six registers 77 - e.g. NASA r=1/2 and k=7 (also in 802.11) — each input bit on left side produces two output bits that are XOR sums of input and internal state: 78 79 